package 中等.双指针;

/**
 * 给你两个字符串 word1 和 word2 。你需要按下述方式构造一个新字符串 merge ：如果 word1
 * 或 word2 非空，选择 下面选项之一 继续操作：
 * <p>
 * 如果 word1 非空，将 word1 中的第一个字符附加到 merge 的末尾，并将其从 word1 中移除。
 * 例如，word1 = "abc" 且 merge = "dv" ，在执行此选项操作之后，word1 = "bc" ，同时 merge = "dva" 。
 * 如果 word2 非空，将 word2 中的第一个字符附加到 merge 的末尾，并将其从 word2 中移除。
 * 例如，word2 = "abc" 且 merge = "" ，在执行此选项操作之后，word2 = "bc" ，同时 merge = "a" 。
 * 返回你可以构造的字典序 最大 的合并字符串 merge 。
 * <p>
 * 长度相同的两个字符串 a 和 b 比较字典序大小，如果在 a 和 b 出现不同的第一个位置，
 * a 中字符在字母表中的出现顺序位于 b 中相应字符之后，就认为字符串 a 按字典序比字
 * 符串 b 更大。例如，"abcd" 按字典序比 "abcc" 更大，因为两个字符串出现不同的第一
 * 个位置是第四个字符，而 d 在字母表中的出现顺序位于 c 之后。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/largest-merge-of-two-strings
 */
public class 构造字典序最大的合并字符串_1754 {

    public static void main(String[] args) {

        // abdcabcabcaba
        // abdcabcabcaba
        System.out.println(largestMerge("abcabc", "abdcaba"));

    }

    /**
     * 双指针+贪心
     * 使用两个指针分别指向word1，word2，优选选择字典序较大的那个字符
     * 如果两个字符串指向的字符相同，那么比较下一个字符的字典序
     */
    public static String largestMerge(String word1, String word2) {
        StringBuilder stringBuilder = new StringBuilder();
        int idx1 = 0, idx2 = 0;

        while (idx1 < word1.length() || idx2 < word2.length()) {
            if (idx1 == word1.length()) {
                stringBuilder.append(word2.substring(idx2));
                return stringBuilder.toString();
            }
            if (idx2 == word2.length()) {
                stringBuilder.append(word1.substring(idx1));
                return stringBuilder.toString();
            }

            int t1 = idx1, t2 = idx2;
            while (t1 < word1.length() && t2 < word2.length() &&
                    word1.charAt(t1) == word2.charAt(t2)) {
                t1++;
                t2++;
            }

            if (t1 == word1.length()) {
                stringBuilder.append(word2.charAt(idx2));
                idx2++;
            } else if (t2 == word2.length()) {
                stringBuilder.append(word1.charAt(idx1));
                idx1++;
            } else {
                if (word1.charAt(t1) > word2.charAt(t2)) {
                    stringBuilder.append(word1.charAt(idx1));
                    idx1++;
                } else {
                    stringBuilder.append(word2.charAt(idx2));
                    idx2++;
                }
            }
        }
        return stringBuilder.toString();
    }

}
